class Solution1 {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for(int i = 0; i<n; i++) {
            if(cost[i] >= gas[i]) {
                 if(check(gas,cost,i)) return i;
            }
        }
        return -1;
    }
    public boolean check(int[] gas, int[] cost, int begin) {
        int sum = 0; //油量
        int t = gas.length;
        while(t-- > 0) {
            sum += gas[begin];
            sum -= cost[begin];
            begin ++;
            if(begin == gas.length) {
                begin = 0;
            }
            if(sum < 0) return false;
        }
        return true;
    }
}

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for(int i = 0; i<n; i++) {
            int rest = 0;
            int step = 0;
            for(step = 0; step < n; step++) {
                int index = (i+step)%n;
                rest = rest + gas[index] - cost[index];
                if(rest < 0) {
                    break;
                }
            }
            if(rest >= 0) {
                return i;
            }
            //优化
            i = i + step;
        }
        return -1;
    }
}

public class Test {
}
